Content addressable memory (CAM) is a useful device for executing table lookup operations. Particularly, because of the parallel lookup capability, a user can execute thousands or even millions of comparisons with one lookup operation.
For computer systems, CAM is widely used as the address lookup table for cache memory (called cache TAG), or as the paging translation look-aside buffer (TLB). For communication applications, CAM is widely used to support address lookup operations for routers. Recently, the rapid growth of networking systems has triggered strong demands for high density and high speed CAM devices. For networking applications, ternary content addressable memory (TCAM) is used to store various items such as quality of service (QoS) information, filter information, access control lists (ACL), etc. A current TCAM for networking application has 256K of 72 bit entries supporting 125 million lookups per second (LPS).
However, due to the parallel lookup operation, CAM devices require support logic, e.g., priority encoders, on their match outputs for determining the TCAM-line address of the stored data that best matches the comparison data. In order to maximize computational speed, follow-on priority encoding logic has been configured for parallel operation. One prior solution utilizes an M:1 priority encoder for an M-entry CAM, as well as M match output flops. As the quantity of entries in a CAM increases, complexity of support priority encoders increase at a faster rate than the number of entries, i.e., approximately M×log M. Increased priority encoder circuit complexity, increases design and manufacturing costs. In addition, significant circuit real estate is consumed by the support prioritizing logic, with physical size quickly becoming a limiting factor in continued expansion of current CAM systems to support maximum application performance. Efficient CAM application is challenging conventional CAM design methodologies.